template <class ItemType>
EnhancedQueue<ItemType>::EnhancedQueue()
// Class constructor.
{
	length = 0;
	queueData = NULL;
}

template <class ItemType>
EnhancedQueue<ItemType>::~EnhancedQueue()
// Class destructor.
{
	NodeType<ItemType>* tempPtr;

    while (queueData != NULL)
    {
        tempPtr = queueData;
        queueData = queueData->next;
        delete tempPtr;
    }
}

template <class ItemType>
EnhancedQueue<ItemType>::EnhancedQueue(const EnhancedQueue &orig)
//copy constructor
{
	queueData = NULL;
		
	if (orig.queueData == NULL)
		return;

	NodeType<ItemType>* sourcePtr;
	sourcePtr = orig.queueData;

	//copy first node
	queueData = new NodeType<ItemType>;

	queueData->info = sourcePtr->info;
	sourcePtr = sourcePtr->next;
	
	//copy rest of nodes
	NodeType<ItemType>* tempPtr;
	tempPtr = queueData;
	while (sourcePtr != NULL)
	{
		tempPtr->next = new NodeType<ItemType>;

		tempPtr = tempPtr->next;
		tempPtr->info = sourcePtr->info;
		sourcePtr = sourcePtr->next;
	}
	tempPtr->next = NULL;
}

template <class ItemType>
EnhancedQueue<ItemType> EnhancedQueue<ItemType>::operator=(const EnhancedQueue<ItemType>& rhs)
//assignment operator
{
	//check x=x
	if(this == &rhs)
		return *this;

	//delete existing nodes
	NodeType<ItemType>* tempPtr;
    while (queueData != NULL)
    {
        tempPtr = queueData;
        queueData = queueData->next;
        delete tempPtr;
    }
    queueData = NULL;
	
	//copy from source	
	if (rhs.queueData == NULL)
		return *this;

	NodeType<ItemType>* sourcePtr;
	sourcePtr = rhs.queueData;

	//copy first node
	queueData = new NodeType<ItemType>;
	queueData->info = sourcePtr->info;
	sourcePtr = sourcePtr->next;
	tempPtr = queueData;
	
	//copy rest of nodes
	while (sourcePtr != NULL)
	{
		tempPtr->next = new NodeType<ItemType>;
		
		tempPtr = tempPtr->next;
		tempPtr->info = sourcePtr->info;
		sourcePtr = sourcePtr->next;
	}
	tempPtr->next = NULL;
	return *this;
}

template <class ItemType>
int EnhancedQueue<ItemType>::Length() const
//returns queue length
{
	return length;
}

template <class ItemType>
void EnhancedQueue<ItemType>::Clear()
//clears queue
{
	NodeType<ItemType>* tempPtr;

    while (queueData != NULL)
    {
        tempPtr = queueData;
        queueData = queueData->next;
        delete tempPtr;
    }
	queueData = NULL;
	length = 0;
}

template <class ItemType>
void EnhancedQueue<ItemType>::MoveLastToFront()
//moves last item to front of queue
{
	//check cases which would have no change
	if (length == 0 || length == 1)
		return;
	else
	{
		MoveLastToFront2(queueData);
	}
}

template <class ItemType>
void EnhancedQueue<ItemType>::MoveLastToFront2(NodeType<ItemType>* &queue)
{
	if (queue->next->next == NULL)
	{
		NodeType<ItemType>* newFront;
		newFront = queue->next;
		newFront->next = queueData;
		queue->next = NULL;
		queueData = newFront;
	}
	else
		MoveLastToFront2(queue->next);
}


template <class ItemType>
bool EnhancedQueue<ItemType>::Move(int from, int to)
//moves item to a different position
{
	//check for illegal values
	if(from > length || to > length || from < 1 || to < 1)
		return false;
	else
	{
		NodeType<ItemType>* fromPtr;
		NodeType<ItemType>* tempPtr;
		NodeType<ItemType>* toPtr;
		tempPtr = queueData;
		
		//if positions are the same, do nothing
		if ( to == from)
			return true;

		//case in which first position is moved
		else if (to == 1)
		{
			//locate position
			for(int i = 1; i < from - 1; i++)
				tempPtr = tempPtr->next;
			//remove from queue
			fromPtr = tempPtr->next;
			tempPtr->next = fromPtr->next;
			//insert in queue
			fromPtr->next = queueData;
			queueData = fromPtr;
		}

		//case in which first position moves elsewhere
		else if (from == 1)
		{
			queueData = queueData->next;
			toPtr = queueData;
			//locate the position
			for(int i = 1; i < to - 1; i++)
				toPtr = toPtr->next;
			//insert in queue
			tempPtr->next = toPtr->next;
			toPtr->next = tempPtr;

		}

		//cases in which first position is not touched
		else
		{
			toPtr = fromPtr = queueData;
			//locate item to be moved
			for(int i = 1; i < from - 1; i++)
				fromPtr = fromPtr->next;
			//take it out of the queue
			tempPtr = fromPtr->next;
			fromPtr->next = fromPtr->next->next;
	
			//locate the spot for it to be placed
			for(int i = 1; i < to - 1; i++)
				toPtr = toPtr->next;
			//insert it in the queue
			tempPtr->next = toPtr->next;
			toPtr->next = tempPtr;
		}

		return true;
	}
}

template <class ItemType>
void EnhancedQueue<ItemType>::Enqueue(ItemType item)
//enqueues an item at the end of the queue
{
	NodeType<ItemType>* newNode;

    newNode = new NodeType<ItemType>;

	newNode->info = item;
    newNode->next = NULL;

	//case if queue is empty
    if (queueData == NULL)
        queueData = newNode;

	//case if queue contains elements
    else
	{
		NodeType<ItemType>* tempPtr;
		tempPtr = queueData;
		//locate end of queue
		while(tempPtr->next != NULL)
			tempPtr = tempPtr->next;
		//add the new item
        tempPtr->next = newNode;
	}
	length++;
}

template <class ItemType>
int EnhancedQueue<ItemType>::Find(ItemType item)
//finds and item in the queue
{
	int pos = 0;
	if (length == 0)
		return -1;
	pos = Find2(item, queueData);
	if (pos > length)
		return -1;
	else
		return pos;	
}

template <class ItemType>
int EnhancedQueue<ItemType>::Find2(ItemType item, NodeType<ItemType>* queue)
{
	if (queue != NULL)
	{
		if (queue->info != item)
			return Find2(item, queue->next) + 1;
		else
			return 1;
	}
	else
		return 1;
}

template <class ItemType>
void EnhancedQueue<ItemType>::Dequeue(ItemType &item)
//dequeues the first position in the queue
{
	item = queueData->info;

    NodeType<ItemType>* tempPtr;
    tempPtr = queueData;
    queueData = queueData->next;
	delete tempPtr;

	length--;
}

template <class ItemType>
void EnhancedQueue<ItemType>::Print(ostream &out)
//prints a list of the elements in the queue
{
	Print2(out, queueData);
}

template <class ItemType>
void EnhancedQueue<ItemType>::Print2(ostream &out, NodeType<ItemType>* queue)
{
	if (queue != NULL)
	{
		out << queue->info << endl;
		Print2(out, queue->next);
	}
}

template <class ItemType>
bool EnhancedQueue<ItemType>::Delete(int pos, ItemType &item)
//deletes an item in the queue
{
	//check for invalid positions
	if(pos > length || pos < 1)
		return false;
	else
	{
		NodeType<ItemType>* tempPtr;

		//case for first position in queue
		if (pos == 1)
		{
			tempPtr = queueData;
			queueData = queueData->next;
			item = tempPtr->info;
			delete tempPtr;
		}

		//case for all other positions
		else
		{
			Delete2(pos, item, queueData);
		}
	}
	length--;
	return true;
}

template <class ItemType>
void EnhancedQueue<ItemType>::Delete2(int pos, ItemType &item, NodeType<ItemType>* &queue)
{
	if (pos == 2)
	{
		NodeType<ItemType>* delPtr;
		delPtr = queue->next;

		queue->next = queue->next->next;
		item = delPtr->info;
		delete delPtr;
	}
	else
		Delete2(pos-1,item,queue->next);

}